/*
 * @lc app=leetcode.cn id=139 lang=java
 *
 * [139] 单词拆分
 */

import java.util.HashSet;
import java.util.List;
import java.util.Set; 

// @lc code=start
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // // 动态规划
        // int len = s.length();
        // boolean[] dp = new boolean[len + 1];

        // dp[0] = true;

        // Set<String> set = new HashSet<>(wordDict);

        // for(int i = 1; i <= len; i++) {
        //     for(int j = 0; j < i; j++) {
        //         if(dp[j] && set.contains(s.substring(j, i))) {
        //             dp[i] = true;
        //             break;
        //         }
        //     }
        // }
        // return dp[len];


        // 动态规划
        int len = s.length();
        Set<String> set = new HashSet<>();
        for(String str : wordDict) {
            set.add(str);
        }

        boolean[] dp = new boolean[len + 1];
        dp[0] = true;

        for(int i = 1; i <= len; i++) {
            for(int j = 1; j <= i && !dp[i]; j++) {
                String str = s.substring(j-1, i);

                if(set.contains(str) && dp[j-1]) {
                    dp[i] = true;
                }
            }
        }
        return dp[len];


    }
}
// @lc code=end

